package leetcode.year2021.month9;

import java.util.LinkedList;
import java.util.Queue;

public class _29_03Connect116 {

  public Node connect(Node root) {
    if (root == null) {
      return root;
    }

    // 从根节点开始
    Node leftmost = root;

    while (leftmost.left != null) {

      // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
      Node head = leftmost;

      while (head != null) {

        // CONNECTION 1
        head.left.next = head.right;

        // CONNECTION 2
        if (head.next != null) {
          head.right.next = head.next.left;
        }

        // 指针向后移动
        head = head.next;
      }

      // 去下一层的最左的节点
      leftmost = leftmost.left;
    }

    return root;

    // 广度优先遍历
//  public Node connect(Node root) {
//    if (root == null){
//      return root;
//    }
//
//    Queue<Node> nodes = new LinkedList<Node>();
//    nodes.add(root);
//
//    while (!nodes.isEmpty()){
//      int size = nodes.size();
//
//      for (int i = 0; i < size; i++) {
//        Node poll = nodes.poll();
//        if (i < size-1){
//          poll.next = nodes.peek();
//        }
//
//        if (poll.left != null){
//          nodes.add(poll.left);
//        }
//        if (poll.right != null){
//          nodes.add(poll.right);
//        }
//      }
//    }
//    return root;
    /**
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     *
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     *
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     */
  }


  class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
      val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
      val = _val;
      left = _left;
      right = _right;
      next = _next;
    }
  }

  ;
}
